/**
 * 打家劫舍-3
 * 每栋房子有且只有一个“父“房子与之相连。
 * 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
 * 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额
 * 输入：root = [3,2,3,null,3,null,1]
 * 输出：7
 */

/**
 * 树形遍历用地推
 * dp[root]的到最后的解；所以用后序遍历： 左-右-根
 */
const rob3 = (root) => {
  //后序遍历？
  const postOrder = node => {
    if(!node) return [0,0]; //[偷，不偷]
    const left = postOrder(node.left);
    const right = postOrder(node.right);
    const rob = node.val + left[1] + right[1]; //偷当前节点
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); //不偷当前节点
    return [rob, notRob];
  }
  const res = postOrder(root);
  return Math.max(res[0], res[1]);
}

// 定义二叉树节点的构造函数
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
/**
 * 根据层序遍历数组(从上到下，从左到右)构建二叉树
 */
function buildTree(arr) {
  if(arr.length ==0 || arr[0]==null) return null;
  const root = new TreeNode(arr[0])
  
  const queue = [root]; //存储待处理的节点，保证按照层序遍历的顺序
  
  let i=1; //从左节点开始

  while(i<arr.length) {
    const currNode = queue.shift(); // arr[i]的父节点
    
    if(arr[i]!==null) {
      currNode.left = new TreeNode(arr[i]);
      queue.push(currNode.left);
    }

    i++; //指向右节点

    if(i<arr.length && arr[i] !== null) {
      currNode.right = new TreeNode(arr[i]);
      queue.push(currNode.right);
    }
    i++; //指向下一个节点
  }
  return root;
}

// const root = [3,2,3,null,3,null,1]; //层序遍历的到的结果
// const rootTree = buildTree(root);
// console.log('打家劫舍-3',rob3(rootTree));